{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Create Binary Tree From Descriptions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #array #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #数组 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: createBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根据描述创建二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>descriptions</code> ，其中 <code>descriptions[i] = [parent<sub>i</sub>, child<sub>i</sub>, isLeft<sub>i</sub>]</code> 表示 <code>parent<sub>i</sub></code> 是 <code>child<sub>i</sub></code> 在 <strong>二叉树</strong> 中的 <strong>父节点</strong>，二叉树中各节点的值 <strong>互不相同</strong> 。此外：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>isLeft<sub>i</sub> == 1</code> ，那么 <code>child<sub>i</sub></code> 就是 <code>parent<sub>i</sub></code> 的左子节点。</li>\n",
    "\t<li>如果 <code>isLeft<sub>i</sub> == 0</code> ，那么 <code>child<sub>i</sub></code> 就是 <code>parent<sub>i</sub></code> 的右子节点。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你根据 <code>descriptions</code> 的描述来构造二叉树并返回其 <strong>根节点</strong> 。</p>\n",
    "\n",
    "<p>测试用例会保证可以构造出 <strong>有效</strong> 的二叉树。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/02/09/example1drawio.png\" style=\"width: 300px; height: 236px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]\n",
    "<strong>输出：</strong>[50,20,80,15,17,19]\n",
    "<strong>解释：</strong>根节点是值为 50 的节点，因为它没有父节点。\n",
    "结果二叉树如上图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/02/09/example2drawio.png\" style=\"width: 131px; height: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>descriptions = [[1,2,1],[2,3,0],[3,4,1]]\n",
    "<strong>输出：</strong>[1,2,null,null,3,4]\n",
    "<strong>解释：</strong>根节点是值为 1 的节点，因为它没有父节点。 \n",
    "结果二叉树如上图所示。 </pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= descriptions.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>descriptions[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= parent<sub>i</sub>, child<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= isLeft<sub>i</sub> &lt;= 1</code></li>\n",
    "\t<li><code>descriptions</code> 所描述的二叉树是一棵有效二叉树</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [create-binary-tree-from-descriptions](https://leetcode.cn/problems/create-binary-tree-from-descriptions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [create-binary-tree-from-descriptions](https://leetcode.cn/problems/create-binary-tree-from-descriptions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]', '[[1,2,1],[2,3,0],[3,4,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: list[list[int]]):\n",
    "        node = {}\n",
    "        has_parent = []\n",
    "        for p, c, is_l in descriptions:\n",
    "            if p not in node:\n",
    "                node[p] = TreeNode(p)\n",
    "            if c not in node:\n",
    "                node[c] = TreeNode(c)\n",
    "            if is_l:\n",
    "                node[p].left = node[c]\n",
    "            else:\n",
    "                node[p].right = node[c]\n",
    "            has_parent.append(c)\n",
    "        for p, t in node.items():\n",
    "            if p not in has_parent:\n",
    "                return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        isRoot={}\n",
    "        nodes={}\n",
    "        for p,c,left in descriptions:\n",
    "            # isRoot里没有p，p暂时没有父结点，设置p暂时是根节点，而c一定不是根节点\n",
    "            if p not in isRoot:\n",
    "                isRoot[p]=True\n",
    "            isRoot[c]=False\n",
    "            # 创建新结点\n",
    "            if p not in nodes:\n",
    "                nodes[p]=TreeNode(p)\n",
    "            if c not in nodes:\n",
    "                nodes[c]=TreeNode(c)\n",
    "            if left==1:\n",
    "                nodes[p].left=nodes[c]\n",
    "            else:\n",
    "                nodes[p].right=nodes[c]\n",
    "        for val,r in isRoot.items():#只有一个val的值为True\n",
    "            if r:\n",
    "                root=val\n",
    "                break\n",
    "        return nodes[root]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        dic = dict()\n",
    "        is_child_node = dict()\n",
    "        for par, child, isleft in descriptions:\n",
    "            if dic.get(par, None) is None:\n",
    "                dic[par] = TreeNode(par)\n",
    "            if dic.get(child, None) is None:\n",
    "                dic[child] = TreeNode(child)\n",
    "            if isleft:\n",
    "                dic[par].left = dic[child]\n",
    "            else:\n",
    "                dic[par].right = dic[child]\n",
    "            is_child_node[child] = True\n",
    "        \n",
    "        for par, child, isleft in descriptions:\n",
    "            if not is_child_node.get(par):\n",
    "                return dic[par]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        treedict = dict()\n",
    "        hasparent = set()\n",
    "        for p, s, v in descriptions:\n",
    "            sontree = treedict.get(s)\n",
    "            if not sontree:\n",
    "                sontree = treedict[s] = TreeNode(s)\n",
    "            \n",
    "            ptree = treedict.get(p)\n",
    "            if not ptree:\n",
    "                ptree = treedict[p] = TreeNode(p)\n",
    "            if v == 1:\n",
    "                ptree.left = sontree\n",
    "            else:\n",
    "                ptree.right = sontree\n",
    "            hasparent.add(s)\n",
    "        for k, v in treedict.items():\n",
    "            if k not in hasparent:\n",
    "                return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        d1={}\n",
    "        d={}\n",
    "        for i in range(len(descriptions)):\n",
    "            a,b,c=descriptions[i][0],descriptions[i][1],descriptions[i][2]\n",
    "            if a not in d1:\n",
    "                d1[a]=1\n",
    "            if b not in d1:\n",
    "                d1[b]=-1 \n",
    "            else:\n",
    "                d1[b]-=1\n",
    "            if a not in d:\n",
    "                d[a]=TreeNode(a)\n",
    "            if b not in d:\n",
    "                d[b]=TreeNode(b)\n",
    "            if c==1:\n",
    "                d[a].left=d[b]\n",
    "            else:\n",
    "                d[a].right=d[b]\n",
    "            \n",
    "        \n",
    "        val=0\n",
    "        for i in d1:\n",
    "            if d1[i]==1:\n",
    "                return d[i]\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        data = {}\n",
    "        is_root = {}\n",
    "        for parent,child,isLeft in descriptions:\n",
    "            if parent not in data:\n",
    "                data[parent]=TreeNode(parent)\n",
    "                is_root[parent] = True\n",
    "            is_root[child] = False\n",
    "            node = data.get(child) or TreeNode(child)\n",
    "            data[child] = node\n",
    "            if isLeft:\n",
    "                data[parent].left=node\n",
    "            else:\n",
    "                data[parent].right=node\n",
    "\n",
    "        root = -1\n",
    "        for k, r in is_root.items():\n",
    "            if r:\n",
    "                root = k\n",
    "                break\n",
    "        return data[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        isRoot = {}   # 数值对应的节点是否为根节点的哈希表\n",
    "        nodes = {}   # 数值与对应节点的哈希表\n",
    "        for p, c, left in descriptions:\n",
    "            if p not in isRoot:\n",
    "                isRoot[p] = True\n",
    "            isRoot[c] = False\n",
    "            # 创建或更新节点\n",
    "            if p not in nodes:\n",
    "                nodes[p] = TreeNode(p)\n",
    "            if c not in nodes:\n",
    "                nodes[c] = TreeNode(c)\n",
    "            if left:\n",
    "                nodes[p].left = nodes[c]\n",
    "            else:\n",
    "                nodes[p].right = nodes[c]\n",
    "        # 寻找根节点\n",
    "        root = -1\n",
    "        for val, r in isRoot.items():\n",
    "            if r:\n",
    "                root = val\n",
    "                break\n",
    "        return nodes[root]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        n = len(descriptions)+1\n",
    "        L = {}\n",
    "        R = {}\n",
    "        SON = set()\n",
    "        for p,c,i in descriptions:\n",
    "            if i:L[p] = c\n",
    "            else:R[p] = c\n",
    "            SON.add(c)\n",
    "        \n",
    "        \n",
    "        rt = -1\n",
    "        for i in L:\n",
    "            if i not in SON:rt = i;break\n",
    "        for i in R:\n",
    "            if i not in SON:rt = i;break\n",
    "        RT = TreeNode(rt)\n",
    "        print(RT)\n",
    "        st = [RT]\n",
    "        while st:\n",
    "            out = st.pop()\n",
    "            if out.val in L:\n",
    "                l = TreeNode(L[out.val])\n",
    "                out.left = l\n",
    "                st.append(l)\n",
    "            if out.val in R:\n",
    "                r = TreeNode(R[out.val])\n",
    "                out.right = r\n",
    "                st.append(r)\n",
    "        return RT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        isRoot = {}\n",
    "        nodes = {}\n",
    "        for p, c, left in descriptions:\n",
    "            if p not in isRoot:\n",
    "                isRoot[p] = True\n",
    "            isRoot[c] = False\n",
    "            if p not in nodes:\n",
    "                nodes[p] = TreeNode(p)\n",
    "            if c not in nodes:\n",
    "                nodes[c] = TreeNode(c)\n",
    "            if left:\n",
    "                nodes[p].left = nodes[c]\n",
    "            else:\n",
    "                nodes[p].right = nodes[c]\n",
    "            \n",
    "        root = -1\n",
    "        for val, r in isRoot.items():\n",
    "            if r:\n",
    "                root = val\n",
    "                break\n",
    "        return nodes[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        isRoot = {}   # 数值对应的节点是否为根节点的哈希表\n",
    "        nodes = {}   # 数值与对应节点的哈希表\n",
    "        for p, c, left in descriptions:\n",
    "            if p not in isRoot:\n",
    "                isRoot[p] = True\n",
    "            isRoot[c] = False\n",
    "            # 创建或更新节点\n",
    "            if p not in nodes:\n",
    "                nodes[p] = TreeNode(p)\n",
    "            if c not in nodes:\n",
    "                nodes[c] = TreeNode(c)\n",
    "            if left:\n",
    "                nodes[p].left = nodes[c]\n",
    "            else:\n",
    "                nodes[p].right = nodes[c]\n",
    "        # 寻找根节点\n",
    "        root = -1\n",
    "        for val, r in isRoot.items():\n",
    "            if r:\n",
    "                root = val\n",
    "                break\n",
    "        return nodes[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        desdic = {}\n",
    "        headdes = {}\n",
    "        for p,c,isl in descriptions:\n",
    "            if p not in desdic.keys():\n",
    "                desdic[p] = TreeNode(p)\n",
    "            if c not in desdic.keys():\n",
    "                desdic[c] = TreeNode(c)\n",
    "            headdes[c] = p\n",
    "            if isl == 1:\n",
    "                desdic[p].left = desdic[c]\n",
    "            else:\n",
    "                desdic[p].right = desdic[c]\n",
    "            # find no head\n",
    "        nodes = desdic.keys()\n",
    "        \n",
    "        for node in nodes:\n",
    "            if node not in headdes.keys():\n",
    "                return desdic[node]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        isRoot = {}\n",
    "        nodes = {}\n",
    "        for p, c, left in descriptions:\n",
    "            if p not in isRoot:\n",
    "                isRoot[p] = True\n",
    "            isRoot[c] = False\n",
    "            if p not in nodes:\n",
    "                nodes[p] = TreeNode(p)\n",
    "            if c not in nodes:\n",
    "                nodes[c] = TreeNode(c)\n",
    "            if left:\n",
    "                nodes[p].left = nodes[c]\n",
    "            else:\n",
    "                nodes[p].right = nodes[c]\n",
    "        \n",
    "        # 寻找根节点\n",
    "        root = -1\n",
    "        for val, r in isRoot.items():\n",
    "            if r:\n",
    "                root = val\n",
    "                break\n",
    "        return nodes[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        node_map = {}\n",
    "        child_set = set()\n",
    "\n",
    "        for des in descriptions:\n",
    "            parent, child, is_left = des\n",
    "\n",
    "            if parent in node_map:\n",
    "                parent_node = node_map[parent]\n",
    "            else:\n",
    "                parent_node = TreeNode(parent)\n",
    "                node_map[parent] = parent_node\n",
    "\n",
    "            if child in node_map:\n",
    "                child_node = node_map[child]\n",
    "            else:\n",
    "                child_node = TreeNode(child)\n",
    "                node_map[child] = child_node\n",
    "        \n",
    "            child_set.add(child)\n",
    "\n",
    "            if is_left:\n",
    "                parent_node.left = child_node\n",
    "            else:\n",
    "                parent_node.right = child_node\n",
    "        \n",
    "        root_ = [i for i in node_map.keys() if i not in child_set][0]\n",
    "\n",
    "        return node_map[root_]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        isRoot = dict()\n",
    "        isNodes = dict()\n",
    "        for parenti, childi, isLefti in descriptions:\n",
    "            if parenti not in isRoot:\n",
    "                isRoot[parenti] = True\n",
    "            isRoot[childi] = False\n",
    "\n",
    "            if parenti not in isNodes:\n",
    "                isNodes[parenti] = TreeNode(parenti)\n",
    "\n",
    "            if childi not in isNodes:\n",
    "                isNodes[childi] = TreeNode(childi)\n",
    "\n",
    "            if isLefti:\n",
    "                isNodes[parenti].left = isNodes[childi]\n",
    "            else:\n",
    "                isNodes[parenti].right = isNodes[childi]\n",
    "\n",
    "        root = None\n",
    "        for k, v in isRoot.items():\n",
    "            if v:\n",
    "                root = isNodes[k]\n",
    "                break\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        d = dict()\n",
    "        cbr = set()  # can be root\n",
    "        cnbr = set()\n",
    "\n",
    "        for pv, cv, il in descriptions:\n",
    "            pn = d.setdefault(pv, TreeNode(pv))\n",
    "            cn = d.setdefault(cv, TreeNode(cv))\n",
    "\n",
    "            if il == 1:\n",
    "                pn.left  = cn\n",
    "            else:\n",
    "                pn.right = cn\n",
    "\n",
    "            if pn not in cnbr:\n",
    "                cbr.add(pn)\n",
    "            \n",
    "            cbr.discard(cn)\n",
    "            cnbr.add(cn)\n",
    "        \n",
    "        return list(cbr)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        nodes = defaultdict(TreeNode)\n",
    "        vals = set()\n",
    "        for x, y, left in descriptions:\n",
    "            if left:\n",
    "                nodes[x].left = nodes[y]\n",
    "            else:\n",
    "                nodes[x].right = nodes[y]\n",
    "            vals.add(y)\n",
    "        for v, node in nodes.items():\n",
    "            node.val = v\n",
    "        return next(node for v, node in nodes.items() if v not in vals)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        nodes = defaultdict(TreeNode)\n",
    "        vals = set()\n",
    "        for v1, v2, left in descriptions:\n",
    "            if left:\n",
    "                nodes[v1].left = nodes[v2]\n",
    "            else:\n",
    "                nodes[v1].right = nodes[v2]\n",
    "            vals.add(v2)\n",
    "        for v, node in nodes.items():\n",
    "            node.val = v\n",
    "        for k, node in nodes.items():\n",
    "            if node.val not in vals:\n",
    "                return node\n",
    "        return None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        nodes = defaultdict(TreeNode)\n",
    "        vals = set()\n",
    "        for x, y, left in descriptions:\n",
    "            if left:\n",
    "                nodes[x].left = nodes[y]\n",
    "            else:\n",
    "                nodes[x].right = nodes[y]\n",
    "            vals.add(y)\n",
    "        for v, node in nodes.items():\n",
    "            node.val = v\n",
    "        return next(node for v, node in nodes.items() if v not in vals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        nodes = defaultdict(TreeNode)\n",
    "        vals = set()\n",
    "        for x, y, left in descriptions:\n",
    "            if left:\n",
    "                nodes[x].left = nodes[y]\n",
    "            else:\n",
    "                nodes[x].right = nodes[y]\n",
    "            vals.add(y)\n",
    "        for v, node in nodes.items():\n",
    "            node.val = v\n",
    "        return next(node for v, node in nodes.items() if v not in vals)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# from typing import *\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        nodes = {}\n",
    "        for (father, child, is_left) in descriptions:\n",
    "            if father not in nodes:\n",
    "                nodes[father] = [ TreeNode(val=father), False ]\n",
    "            if child not in nodes:\n",
    "                nodes[child] = [ TreeNode(val=child), False ]\n",
    "            if is_left == 1:\n",
    "                nodes[father][0].left = nodes[child][0]\n",
    "                nodes[child][1] = True\n",
    "            else:\n",
    "                nodes[father][0].right = nodes[child][0]\n",
    "                nodes[child][1] = True\n",
    "        for (node, flag) in nodes.values():\n",
    "            if not flag:\n",
    "                return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        d = defaultdict(TreeNode)\n",
    "        child = set()\n",
    "        for p, c, isL in descriptions:\n",
    "            if isL:\n",
    "                d[p].left = d[c]\n",
    "            else:\n",
    "                d[p].right = d[c]\n",
    "            child.add(c)\n",
    "        for v, node in d.items():\n",
    "            node.val = v \n",
    "        for k in d:\n",
    "            if k not in child:\n",
    "                return d[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        h = defaultdict(TreeNode)\n",
    "        roots = set()\n",
    "        childs = set()\n",
    "        for p, c, isLeft in descriptions:\n",
    "            h[c].val = c\n",
    "            h[p].val = p\n",
    "            if isLeft: h[p].left = h[c]\n",
    "            else: h[p].right = h[c]\n",
    "            if p not in childs: roots.add(p)\n",
    "            childs.add(c)\n",
    "            if c in roots: roots.remove(c)\n",
    "        return h[list(roots)[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        tree = defaultdict(TreeNode)\n",
    "        childrens = set()\n",
    "        for p, c, l in descriptions:\n",
    "            childrens.add(c)\n",
    "            tree[p].val = p\n",
    "            tree[c].val = c\n",
    "            if l:\n",
    "                tree[p].left = tree[c]\n",
    "            else:\n",
    "                tree[p].right = tree[c]\n",
    "\n",
    "        return tree[next(n for n in tree if n not in childrens)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        memo = dict()\n",
    "        for desc in descriptions:\n",
    "            par = desc[0]\n",
    "            ch = desc[1]\n",
    "            isLeft = desc[2] == 1\n",
    "            if par not in memo:\n",
    "                memo[par] = TreeNode(par)\n",
    "            if ch not in memo:\n",
    "                memo[ch] = TreeNode(ch)\n",
    "            if isLeft:\n",
    "                memo[par].left = memo[ch]\n",
    "            else:\n",
    "                memo[par].right = memo[ch]\n",
    "        rootSet = set(memo.keys())\n",
    "        for node in memo.values():\n",
    "            if node.left:\n",
    "                rootSet.remove(node.left.val)\n",
    "            if node.right:\n",
    "                rootSet.remove(node.right.val)\n",
    "        return memo[rootSet.pop()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        val2node = {}\n",
    "        has_pa = set()\n",
    "        for pa, ch, is_left in descriptions:\n",
    "            if pa in val2node:\n",
    "                pa_node = val2node[pa]\n",
    "                ch_node = TreeNode(val=ch) if ch not in val2node else val2node[ch]\n",
    "                if is_left:\n",
    "                    pa_node.left = ch_node\n",
    "                else:\n",
    "                    pa_node.right = ch_node\n",
    "                val2node[ch] = ch_node\n",
    "            else:\n",
    "                ch_node = TreeNode(val=ch) if ch not in val2node else val2node[ch]\n",
    "                if is_left:\n",
    "                    pa_node = TreeNode(val=pa, left=ch_node)\n",
    "                else:\n",
    "                    pa_node = TreeNode(val=pa, right=ch_node)\n",
    "                val2node[pa] = pa_node\n",
    "                val2node[ch] = ch_node\n",
    "            has_pa.add(ch)\n",
    "            # print(val2node[pa])\n",
    "        for v in val2node:\n",
    "            if v not in has_pa:\n",
    "                return val2node[v]\n",
    "        \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        nodes = defaultdict(TreeNode)\n",
    "        vals = set()\n",
    "        for x, y, left in descriptions:\n",
    "            if left:\n",
    "                nodes[x].left = nodes[y]\n",
    "            else:\n",
    "                nodes[x].right = nodes[y]\n",
    "            vals.add(y)\n",
    "        for v, node in nodes.items():\n",
    "            node.val = v\n",
    "        return next(node for v, node in nodes.items() if v not in vals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        n = len(descriptions)\n",
    "        d = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            [fv, sv, isLeft] = descriptions[i]\n",
    "            if fv not in d.keys():\n",
    "                d[fv] = [TreeNode(fv), False]\n",
    "            if sv not in d.keys():\n",
    "                d[sv] = [TreeNode(sv), False]\n",
    "            \n",
    "            d[sv][1] = True\n",
    "            \n",
    "            if isLeft == 1:\n",
    "                d[fv][0].left = d[sv][0]\n",
    "            else:\n",
    "                d[fv][0].right = d[sv][0]\n",
    "        \n",
    "        for k in d.keys():\n",
    "            if not d[k][1]:\n",
    "                return d[k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        n = len(descriptions)\n",
    "        d = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            [fv, sv, isLeft] = descriptions[i]\n",
    "            if fv not in d.keys():\n",
    "                d[fv] = [TreeNode(fv), False]\n",
    "            if sv not in d.keys():\n",
    "                d[sv] = [TreeNode(sv), False]\n",
    "            \n",
    "            d[sv][1] = True\n",
    "            \n",
    "            if isLeft == 1:\n",
    "                d[fv][0].left = d[sv][0]\n",
    "            else:\n",
    "                d[fv][0].right = d[sv][0]\n",
    "        \n",
    "        for k in d.keys():\n",
    "            if not d[k][1]:\n",
    "                return d[k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        n = len(descriptions)\n",
    "        d = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            [fv, sv, isLeft] = descriptions[i]\n",
    "            if fv not in d.keys():\n",
    "                d[fv] = [TreeNode(fv), False]\n",
    "            if sv not in d.keys():\n",
    "                d[sv] = [TreeNode(sv), False]\n",
    "            \n",
    "            d[sv][1] = True\n",
    "            \n",
    "            if isLeft == 1:\n",
    "                d[fv][0].left = d[sv][0]\n",
    "            else:\n",
    "                d[fv][0].right = d[sv][0]\n",
    "        \n",
    "        for k in d.keys():\n",
    "            if not d[k][1]:\n",
    "                return d[k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        tree_search_dict = {}\n",
    "        count_father = []\n",
    "        count_son = []\n",
    "        for description_i in descriptions:\n",
    "            if not (description_i[0] in tree_search_dict.keys()):\n",
    "                tree_search_dict[description_i[0]] = TreeNode(val = description_i[0], left = None, right = None)\n",
    "            if not (description_i[1] in tree_search_dict.keys()):\n",
    "                tree_search_dict[description_i[1]] = TreeNode(val = description_i[1], left = None, right = None)\n",
    "            if(description_i[2] == 1):\n",
    "                tree_search_dict[description_i[0]].left = tree_search_dict[description_i[1]]\n",
    "            else:\n",
    "                tree_search_dict[description_i[0]].right = tree_search_dict[description_i[1]]\n",
    "            count_father.append(description_i[0])\n",
    "            count_son.append(description_i[1])\n",
    "        root = list(set(count_father) - set(count_son))[0]\n",
    "        return tree_search_dict[root]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        table = {}\n",
    "        def newNode(val):\n",
    "            if val not in table:\n",
    "                table[val] = TreeNode(val=val)\n",
    "            return table[val]\n",
    "        cld = set()\n",
    "        for root,val,code in descriptions:\n",
    "            root = newNode(root)\n",
    "            if code==1:\n",
    "                root.left = newNode(val)\n",
    "                cld.add(val)\n",
    "            else:\n",
    "                root.right = newNode(val)\n",
    "                cld.add(val)\n",
    "        return table[(set(table.keys())-cld).pop()]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        # 图\n",
    "        tree = defaultdict(TreeNode)\n",
    "        pp = set()\n",
    "        cc = set()\n",
    "        for p, c, l in descriptions:\n",
    "            root = tree[p]\n",
    "            root.val = p\n",
    "            pp.add(p)\n",
    "            cc.add(c)\n",
    "            tree[c].val = c\n",
    "            if l:\n",
    "                root.left = tree[c]\n",
    "            else:\n",
    "                root.right = tree[c]\n",
    "            \n",
    "        return tree[(pp - cc).pop()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        parent = set()\n",
    "        child = set()\n",
    "        for i in range(len(descriptions)):\n",
    "            parent.add(descriptions[i][0])\n",
    "            child.add(descriptions[i][1])\n",
    "        rval = (parent - child).pop()\n",
    "        root = TreeNode(rval)\n",
    "\n",
    "        nodes = {}\n",
    "\n",
    "        for i in range(len(descriptions)):\n",
    "            parent_val = descriptions[i][0]\n",
    "            child_val = descriptions[i][1]\n",
    "            if child_val not in nodes:\n",
    "                nodes[child_val] = TreeNode(child_val)\n",
    "            if parent_val not in nodes:\n",
    "                nodes[parent_val] = TreeNode(parent_val)\n",
    "            if descriptions[i][2]:\n",
    "                nodes[parent_val].left = nodes[child_val]\n",
    "            else:\n",
    "                nodes[parent_val].right = nodes[child_val]\n",
    "        \n",
    "        return nodes[rval]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        dic = dict()\n",
    "        n = len(descriptions)\n",
    "        childs = [i[1] for i in descriptions]\n",
    "        root_key = None\n",
    "        for parenti, childi, isLefti in descriptions:\n",
    "            cur = TreeNode(childi)\n",
    "\n",
    "            if parenti in dic:\n",
    "                par = dic[parenti]\n",
    "            else:\n",
    "                par = TreeNode(parenti)\n",
    "\n",
    "            if parenti not in childs:\n",
    "                root_key = parenti\n",
    "            dic[parenti] = par\n",
    "            if isLefti:\n",
    "                par.left = cur\n",
    "            else:\n",
    "                par.right = cur\n",
    "\n",
    "        root = dic[root_key]\n",
    "\n",
    "        dp = deque([root])\n",
    "        while dp:\n",
    "            cur = dp.popleft()\n",
    "            if cur.left and cur.left.val in dic:\n",
    "                cur.left = dic[cur.left.val]\n",
    "                dp.append(cur.left)\n",
    "            if cur.right and cur.right.val in dic:\n",
    "                cur.right = dic[cur.right.val]\n",
    "                dp.append(cur.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        nodeDict={}\n",
    "        ans=set()\n",
    "        chans=set()\n",
    "        for i in descriptions:\n",
    "            nodeDict[i[0]]=TreeNode(i[0]) \n",
    "            nodeDict[i[1]]=TreeNode(i[1])\n",
    "            ans.add(i[0])\n",
    "            chans.add(i[1])\n",
    "        for i in descriptions:  \n",
    "            if i[2]==1:\n",
    "                nodeDict[i[0]].left=nodeDict[i[1]]\n",
    "            else:\n",
    "                nodeDict[i[0]].right=nodeDict[i[1]]\n",
    "        # print(nodeDict)\n",
    "        # print(ans)\n",
    "        # print(list(ans.difference(chans))[0])\n",
    "        return nodeDict[list(ans.difference(chans))[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        d = defaultdict(list)\n",
    "        child = set()\n",
    "        for p, c, isL in descriptions:\n",
    "            d[p].append((c, isL))\n",
    "            child.add(c)\n",
    "        for k in d:\n",
    "            if k not in child:\n",
    "                root = TreeNode(k)\n",
    "                break\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp, q = q,[]\n",
    "            for node in tmp:\n",
    "                for v, isL in d[node.val]:\n",
    "                    if isL:\n",
    "                        node.left = TreeNode(v)\n",
    "                        q.append(node.left)\n",
    "                    else:\n",
    "                        node.right = TreeNode(v)\n",
    "                        q.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        g = defaultdict(list)\n",
    "        seen = set()\n",
    "        for p, c, v in descriptions:\n",
    "            g[p].append((c, v))\n",
    "            seen.add(c)\n",
    "        \n",
    "        for p, c, v in descriptions:\n",
    "            if p not in seen:\n",
    "                root = TreeNode(p)\n",
    "                break\n",
    "        \n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            v = node.val\n",
    "            for c, v in g[v]:\n",
    "                ch = TreeNode(c)\n",
    "                if v == 1:\n",
    "                    node.left = ch\n",
    "                else:\n",
    "                    node.right = ch\n",
    "                q.append(ch)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        indegree = set()\n",
    "        outdegree = set()\n",
    "        for parent, child, _ in descriptions:\n",
    "            indegree.add(parent)\n",
    "            outdegree.add(child)\n",
    "        \n",
    "        s = indegree - outdegree\n",
    "        root_val = s.pop()\n",
    "\n",
    "        node_mp = {}\n",
    "        for ele in list(indegree | outdegree):\n",
    "            node_mp[ele] = TreeNode(val = ele)\n",
    "        \n",
    "        \n",
    "        for p, c, isLeft in descriptions:\n",
    "            if isLeft == 1:\n",
    "                node_mp[p].left = node_mp[c]\n",
    "            else:\n",
    "                node_mp[p].right = node_mp[c]\n",
    "        \n",
    "\n",
    "        return node_mp[root_val]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        node_child = {}\n",
    "\n",
    "        children = [item[1] for item in descriptions]\n",
    "        for node in [item[0] for item in descriptions]:\n",
    "            if node not in children:\n",
    "                head_val = node\n",
    "\n",
    "        for description in descriptions:\n",
    "            if description[0] not in node_child:\n",
    "                if description[2] == 1:\n",
    "                    node_child[description[0]] = [description[1], None]\n",
    "                else:\n",
    "                    node_child[description[0]] = [None, description[1]]\n",
    "            else:\n",
    "                if description[2] == 1:\n",
    "                    node_child[description[0]][0] = description[1]\n",
    "                else:\n",
    "                    node_child[description[0]][1]= description[1]\n",
    "\n",
    "        # 递归从根节点构造树结构\n",
    "        def build_tree(root):\n",
    "            left = None\n",
    "            right = None\n",
    "            if root in node_child:\n",
    "                if node_child[root][0]:\n",
    "                    left = build_tree(node_child[root][0])\n",
    "                if node_child[root][1]:\n",
    "                    right = build_tree(node_child[root][1])\n",
    "            return TreeNode(root, left, right)\n",
    "            \n",
    "        return build_tree(head_val)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        node_child = {}\n",
    "\n",
    "        children = [item[1] for item in descriptions]\n",
    "        for node in [item[0] for item in descriptions]:\n",
    "            if node not in children:\n",
    "                head_val = node\n",
    "\n",
    "        for description in descriptions:\n",
    "            if description[0] not in node_child:\n",
    "                if description[2] == 1:\n",
    "                    node_child[description[0]] = [description[1], None]\n",
    "                else:\n",
    "                    node_child[description[0]] = [None, description[1]]\n",
    "            else:\n",
    "                if description[2] == 1:\n",
    "                    node_child[description[0]][0] = description[1]\n",
    "                else:\n",
    "                    node_child[description[0]][1]= description[1]\n",
    "\n",
    "        # 递归从根节点构造树结构\n",
    "        def build_tree(root):\n",
    "            left = None\n",
    "            right = None\n",
    "            if root in node_child:\n",
    "                if node_child[root][0]:\n",
    "                    left = build_tree(node_child[root][0])\n",
    "                if node_child[root][1]:\n",
    "                    right = build_tree(node_child[root][1])\n",
    "            return TreeNode(root, left, right)\n",
    "            \n",
    "        return build_tree(head_val)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        m = defaultdict(lambda :[None, None])\n",
    "        ind = defaultdict(int)\n",
    "        for root, node, side in descriptions:\n",
    "            m[root][1-side] = node\n",
    "            ind[node] += 1\n",
    "            ind[root]\n",
    "       \n",
    "        for k in m:\n",
    "            if ind[k] == 0:\n",
    "                root = TreeNode(val=k)\n",
    "                break\n",
    "        \n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            if m[root.val][0] is not None:\n",
    "                root.left = TreeNode(val=m[root.val][0])\n",
    "            if m[root.val][1] is not None:\n",
    "                root.right = TreeNode(val=m[root.val][1])\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return root\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        s=set()\n",
    "        dleft=defaultdict(int)\n",
    "        dright=defaultdict(int)\n",
    "        for i,j,k in descriptions:\n",
    "            s.add(j)\n",
    "            if k==0:\n",
    "                dright[i]=j\n",
    "            else :\n",
    "                dleft[i]=j\n",
    "        root=-1\n",
    "        for i,j,k in descriptions:\n",
    "            if i not in s:\n",
    "                root=i \n",
    "                break\n",
    "        node=TreeNode(root)\n",
    "        def dfs(node):\n",
    "            if node.val==0:\n",
    "                node=None\n",
    "                return\n",
    "            if dleft[node.val]>0:\n",
    "                node.left=TreeNode(dleft[node.val])\n",
    "                dfs(node.left)\n",
    "            if dright[node.val]>0:\n",
    "                node.right=TreeNode(dright[node.val])\n",
    "                dfs(node.right)\n",
    "        dfs(node)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        graph = {}\n",
    "        total_set = set()\n",
    "        child_set = set()\n",
    "        for p, c, l in descriptions:\n",
    "            if(p not in graph):\n",
    "                graph[p] = [None, None]\n",
    "            if(l == 1):\n",
    "                graph[p][0] = c \n",
    "            else:\n",
    "                graph[p][1] = c \n",
    "            total_set.add(p)\n",
    "            total_set.add(c)\n",
    "            child_set.add(c)\n",
    "        root_val = (total_set - child_set).pop()\n",
    "        def dfs(val):\n",
    "            if(not val):\n",
    "                return None\n",
    "            root = TreeNode(val=val)\n",
    "            if(val in graph):\n",
    "                root.left = dfs(graph[val][0])\n",
    "                root.right = dfs(graph[val][1])\n",
    "            return root\n",
    "        return dfs(root_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        graph = {}\n",
    "        total_set = set()\n",
    "        child_set = set()\n",
    "        for p, c, l in descriptions:\n",
    "            if(p not in graph):\n",
    "                graph[p] = [None, None]\n",
    "            if(l == 1):\n",
    "                graph[p][0] = c \n",
    "            else:\n",
    "                graph[p][1] = c \n",
    "            total_set.add(p)\n",
    "            total_set.add(c)\n",
    "            child_set.add(c)\n",
    "        root_val = (total_set - child_set).pop()\n",
    "        def dfs(val):\n",
    "            if(not val):\n",
    "                return None\n",
    "            root = TreeNode(val=val)\n",
    "            if(val in graph):\n",
    "                root.left = dfs(graph[val][0])\n",
    "                root.right = dfs(graph[val][1])\n",
    "            return root\n",
    "        return dfs(root_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        graph = {}\n",
    "        total_set = set()\n",
    "        child_set = set()\n",
    "        for p, c, l in descriptions:\n",
    "            if(p not in graph):\n",
    "                graph[p] = [None, None]\n",
    "            if(l == 1):\n",
    "                graph[p][0] = c \n",
    "            else:\n",
    "                graph[p][1] = c \n",
    "            total_set.add(p)\n",
    "            total_set.add(c)\n",
    "            child_set.add(c)\n",
    "        root_val = (total_set - child_set).pop()\n",
    "        def dfs(val):\n",
    "            if(not val):\n",
    "                return None\n",
    "            root = TreeNode(val=val)\n",
    "            if(val in graph):\n",
    "                root.left = dfs(graph[val][0])\n",
    "                root.right = dfs(graph[val][1])\n",
    "            return root\n",
    "        return dfs(root_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:\n",
    "        isroot=set()\n",
    "        tree_dic=collections.defaultdict(list)\n",
    "        for p, ch, l in descriptions:\n",
    "            tree_dic[p].append([ch, l])\n",
    "            if ch not in isroot:\n",
    "                isroot.add(ch)\n",
    "            \n",
    "        for k in tree_dic.keys():\n",
    "            if k not in isroot:\n",
    "                root_val=k\n",
    "                break\n",
    "        \n",
    "        def buildTree(root_val:int):\n",
    "            root=TreeNode(root_val)\n",
    "            for v in tree_dic[root_val]:\n",
    "                if v[1]==1:\n",
    "                    root.left=buildTree(v[0])\n",
    "                else:\n",
    "                    root.right=buildTree(v[0])\n",
    "            return root\n",
    "        \n",
    "        return buildTree(root_val)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
